// const climbStairs = function(n) {
//     if(n==1) return 1;
//     if(n==2) return 2;
//     return climbStairs(n-1) + climbStairs(n-2);
// }

// const f = [];
// const climbStairs = function (n) {
//     if (n == 1) return 1;
//     if (n == 2) return 2;
//     if (f[n] === undefined) f[n] = climbStairs(n - 1) + climbStairs(n - 2);
//     return f[n];
// }

// dp 动态规划
const climbStairs = function(n) {
    // dp 数组
    const dp = [];
    dp[1]=1;
    dp[2]=2;
    for(let i=3;i<=n;i++) {
        dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
    }
    return dp[n];
}